#
# @lc app=leetcode.cn id=455 lang=python3
#
# [455] 分发饼干
#
# https://leetcode-cn.com/problems/assign-cookies/description/
#
# algorithms
# Easy (57.50%)
# Likes:    446
# Dislikes: 0
# Total Accepted:    182.7K
# Total Submissions: 317.7K
# Testcase Example:  '[1,2,3]\n[1,1]'
#
# 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
# 
# 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >=
# g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
# 
# 
# 示例 1:
# 
# 
# 输入: g = [1,2,3], s = [1,1]
# 输出: 1
# 解释: 
# 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
# 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
# 所以你应该输出1。
# 
# 
# 示例 2:
# 
# 
# 输入: g = [1,2], s = [1,2,3]
# 输出: 2
# 解释: 
# 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
# 你拥有的饼干数量和尺寸都足以让所有孩子满足。
# 所以你应该输出2.
# 
# 
# 
# 
# 提示：
# 
# 
# 1 
# 0 
# 1 
# 
# 
#
# %%
from typing import List
# @lc code=start
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        counter = 0
        child_index = 0
        # initial
        g.sort(reverse=True)
        # 饼的数量是上限；最大饼，去适配，最大小孩
        for bing in sorted(s, reverse=True):
            # 依次取出最大饼
            for index, child in enumerate(g[child_index:]):
                # 依次找到最大小孩
                if bing >= child:
                    # 最大饼，满足，最大小孩，那么，计数一个。
                    counter += 1
                    # 从下一个最大小孩找起
                    child_index += index + 1
                    # 这个饼，就用完了，直接下一个饼
                    break
        return counter

# @lc code=end
solutin = Solution()
solutin.findContentChildren([1, 2], [1,2,3])
